The present invention deals with the area of encryption and decryption of data messages. Encryption takes a cleartext message and produces an encrypted message also called a ciphertext. Decryption takes an encrypted message and produces its corresponding cleartext message.
It is known in the prior art how to take a message and turn it into an encrypted message using a first user's public key. The first user upon receiving the encrypted message can then decrypt it, to reveal the original message, using the first user's secret key. The first user's public key is as the name implies, available to the public so that others can send messages to the first user. However, the first user's secret key is not available. The public key is associated with a one-way function, i.e. once the message is encrypted it cannot be decrypted without the secret key even though the public key and the encryption algorithms are known.
El Gamal encryption is a standard method of encryption known in the art. In this method a first processor performing the encryption step, takes a message m as an input; chooses a random value “c”, and produces the outputs a=m*yc modulo p; b=gc modulo p. For El Gamal decryption, a second processor (which may be the first processor) calculates the data message m from m=a/bx modulo p. In the above y=gx modulo p is the public key and x is the secret key. The parameters g, x, and p and other system parameters are picked according to methods known to a person skilled in the art. The parameter g is a generator of the group Gp. If we take all possible values of x and compute gx, this result will take all values in the group Gp which is a large set of values. The value c is chosen at random by the entity that performs the encryption.
The ElGamal encryption method has the following weaknesses:                (1) Given an encryption (a,b) of an unknown data message m, it is possible to produce an encryption of a still unknown message, which corresponds to the value dm, by computing (a d modulo p, b). For example, if (a,b) is an encryption of the value m=3, then (a′,b′)=(4a,b) is an encryption of the value 4m=12. It is not necessary to know m to compute (a′,b′) from (a,b).        (2) Given the encryption pair of ciphertext (a,b) of data message m, it is possible to produce a ciphertext of md as (admodulo p, bd). For example, a correct message could be raised to some exponent and there would be no way of telling that that had occurred.        (3) Given two ciphertexts (a1, b1) and (a2, b2), with (a1, b1) being an encryption of m1 and (a2, b2) being an encryption of m2, it is possible to produce a ciphertext of the product of m1*m2 modulo p as (a1*a2 modulo p, b1*b2 modulo p).        
These three disadvantages and other and related ones are referred to in literature as malleability. Malleability is a threat to security, correctness of decryption of a message, and privacy in many situations. For example in an auction scenario if an offer for a product by a first individual is m, given the ciphertext a second individual can overbid and make his offer 2*m without knowing how much “m” is but knowing that the second individual will win the bidding process. Using a similar attack one can duplicate votes in an election to determine (later when all votes are decrypted) what you voted (by looking for a duplicate). In the prior art malleability is avoided by forcing the value of the data message m to be encrypted to be of a particular form, such as to always end in a particular string of length approximately 100 bits. This technique of avoiding malleability has two disadvantages:                (a) First, it is not possible to determine that an encrypted message is of the valid form without decrypting it.        (b) Secondly, this is not known to result in a problem-free system (i.e. a ‘non-malleable encryption’) and cannot be proved to result in a non-malleable encryption.        
However, prior to the parent application there were no approaches better at dealing with the malleability problem without losing efficiency of the resulting scheme and ciphertext.
The parent application provides a non-malleable encryption method where an encryption technique and a signing technique are used. An encryption processor takes a data message and produces an encryption using an encryption process. The encryption may also be called a ciphertext and typically would be comprised of first and second ciphertext portions. A signing processor takes the encryption and adds a signature to the first and second ciphertext portions using, for example, the second ciphertext portion as the public key for the signature. A receiver processor receives the ciphertext and the signature, decrypts the ciphertext to form a first data message, and determines if the first data message is valid by verifying the signature.
The encryption processor of the parent application may employ ElGamal encryption for the encryption process to form the encryption. The signing processor may perform a Schnorr signature process for the signing process or any other similar discrete log based signature, as appreciated by those skilled in the art. The signing processor may use part of the encryption process to perform the signing process.